public class MinHeap<T extends Comparable<T>> {

    private Array<T> array;

    public MinHeap(){
        array = new Array<>();
    }

    public MinHeap(int capacity){
        array = new Array<>(capacity);
    }

    //返回堆中的元素个数
    public int size(){
        return array.getSize();
    }

    //判断堆是否为空
    public boolean isEmpty(){
        return array.isEmpty();
    }

    //返回完全二叉树的数组中，一个索引所表示的元素的父亲节点的索引
    public int parent(int index){
        return (index-1) / 2;
    }

    //返回完全二叉树的数组中，一个索引所表示的元素的左孩子节点的索引
    public int leftChild(int index){
        return index * 2 + 1;
    }

    //返回完全二叉树的数组中，一个索引所表示的元素的右孩子节点的索引
    public int rightChild(int index){
        return index * 2 + 2;
    }

    //向堆中插入元素
    /*
        1、添加进数组中
        2、sift up(调整堆中的元素，使其满足每个节点都要小于其左右孩子节点)
     */
    public void add(T t){
        array.addLast(t);
        siftUp(array.getSize() - 1);
    }

    private void siftUp(int index){
        while (index > 0 && array.get(parent(index)).compareTo(array.get(index)) > 0){
            array.swap(index,parent(index));
            index = parent(index);
        }
    }

    //看堆中最小的元素
    public T findMin(){
        return array.get(0);
    }

    //取出堆中最小的元素
    public T extractMin(){
        T min = findMin();
        array.set(0,array.getLast());
        array.removeLast();
        siftDown(0);

        return min;
    }

    private void siftDown(int index){
        while (leftChild(index) < array.getSize()){
            int j = leftChild(index);
            if(rightChild(index) < array.getSize() && array.get(rightChild(index)).compareTo(array.get(j))<0){
                j = rightChild(index);
            }
            //此时，data[j]的值就是左孩子和右孩子之中的最小值

            if(array.get(index).compareTo(array.get(j)) <0){
                break;
            }

            array.swap(index,j);
            index = j;
        }
    }
}
